package 堆.练习;
//最大或者最小的前k个数据
import java.util.Comparator;
import java.util.PriorityQueue;
class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Text_1 {
    //求最大的k个元素
    public int[] maxKK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr==null||k<=0){
            return ret;
        }
        //默认最小堆，通过使用比较器，变成默认最大堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            queue.offer(arr[i]);
        }
        //每次弹出的就是最大的
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    //求前k个最小值
    public int[] MinK(int[] array,int k){
        int[] ret = new int[k];
        if(k<=0||array == null){
            return ret;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());
        //将数组的前k个元素入队列
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }

        for (int i = k; i < array.length; i++) {
            //队列中的最大值
            int x = queue.peek();
            //将最大的弹出去，将这个小的放进来
            if(array[i] < x){
                queue.poll();
                queue.offer(array[i]);
            }
        }
        //将队列中的最大值依次放入数组
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }

        return ret;
    }


    //找出最大的k个数
    public int[] maxK(int[] array,int k){
        int[] ret = new int[k];
        if(k<=0||array == null){
            return ret;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }

        for (int i = k; i < array.length; i++) {
            int x = queue.peek();
            if(array[i]>x){
                queue.poll();
                queue.offer(array[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] array ={1,5,9,2,5,4};
        Text_1 text1 =new Text_1();
        int[] ret = text1.maxK(array,4);
        for (int x :ret){
            System.out.print(x+" ");
        }
        System.out.println();
        int[] ret1 = text1.MinK(array,5);
        for (int x :ret1){
            System.out.print(x+" ");
        }
    }
}

